package tree

import (
	"fmt"
)

// avl 树， 二叉搜索树
// 隐式继承 二叉树的东西
// avl 树在插入时， 最好做后续遍历插入， 这样在插入的同时好计算高度差， 方便在插入的同时进行调整
func CreateAVLTree(data []interface{}){
	root := NewAvlTree()
	root.Value = data[0]
	for _, v := range data[1:]{
		node := NewAvlTree()
		node.Value = v
		root = AVLInsert(root, node)
	}
	var InOrder = func (root *AvlTree) (res []interface{}) {
		res = make([]interface{}, 0, 1024)
		if root == nil {
			return nil
		}
		var dfs func(node *AvlTree)
		dfs = func(node *AvlTree) {
			if node == nil {
				return
			}
			res = append(res, node.String())
			dfs(node.LChild)
			dfs(node.RChild)
		}
		dfs(root)
		return
	}
	fmt.Println(InOrder(root))
}
type AvlTree struct {
	Value interface{}
	CoverCounter int
	Height int
	LChild *AvlTree
	RChild *AvlTree
	// Index  int //样例中是以index来进行排序的， 这里我就是用二叉树中的value大小进行排序
}

func (avl *AvlTree)String()string{
	return fmt.Sprintf("self:%p Val:%v L:%p R:%p H:%d\n",avl, avl.Value, avl.LChild, avl.RChild, avl.Height)
}

func NewAvlTree()*AvlTree{
	return new(AvlTree)
}
func (a *AvlTree)GetHeight()int {
	if a == nil {
		return 0
	}
	return a.Height
}

func (avl *AvlTree)CountHeight(){
	if avl.GetLeftChild() == nil && avl.GetRightChild() == nil {
		avl.Height = 0
	}else{
		var max = func (a, b int)int{
			if a > b {
				return a
			}
			return b
		}
		avl.Height = max(avl.LChild.GetHeight(), avl.RChild.GetHeight()) + 1
	}
}

func (avl *AvlTree)GetLeftChild()BinTree{
	if avl.LChild == nil {
		return nil
	}
	return avl.LChild
}

func (avl *AvlTree)SetLeftChild(node BinTree){
	avl.LChild , _ = node.(*AvlTree)
}

func (avl *AvlTree)GetRightChild()BinTree{
	if avl.RChild == nil {
		return nil
	}
	return avl.RChild
}

func (avl *AvlTree)SetRightChild(node BinTree){
	avl.RChild , _ = node.(*AvlTree)
}

func (avl *AvlTree)GetData()interface{}{
	return avl.Value
}

func (avl *AvlTree)SetData(data interface{}){
	avl.Value = data
}

// 改造成迭代的话，需要一个栈空间来模拟
func AVLInsert(avl, node *AvlTree)(root *AvlTree){
	if node == nil {
		return nil
	}
	if avl == nil || avl.Value == nil {
		return node
	}
	cur := avl
	res , err := Compare(cur ,node)
	if err != nil {
		return nil
	}
	//fmt.Println(cur , node, res)
	switch res {
	case -1 :
		cur.RChild = AVLInsert(cur.RChild, node)
	case 0 :
		cur.CoverCounter++
	case 1:
		cur.LChild = AVLInsert(cur.LChild,node)
	}
	//计算高度
	cur.CountHeight()
	// 调整高度
	cur = cur.HandleBF()
	return cur
}

// LL型 左子树 的 左子树 更高
// 		  oldAvl			  newAvl
//			/				  /	  \
//  	 newAvl		->	    L1    oldAvl
//	  	  / \				    	/
//		L1	R1				       R1
func (avl *AvlTree)LLRotation()*AvlTree{
	// oldAvl := avl
	// newAvl := oldAvl.LChild
	// oldAvl.LChild = newAvl.RChild
	// newAvl.RChild = oldAvl
	// oldAvl.CountHeight()
	// newAvl.CountHeight()

	bt := LLRotation(avl)
	newAvl, _ := bt.(*AvlTree)
	newAvl.RChild.CountHeight()
	newAvl.CountHeight()
	return newAvl
}

// RR型 右子树 的 右子树 更高
//    oldAvl             newAvl
//        \              /   \
//      newAvl  ->   oldAvl  R1
//       /   \           \ 
//     L1    R1          L1    
func (avl *AvlTree)RRRotation()*AvlTree{
	// oldAvl := avl
	// newAvl := oldAvl.RChild
	// oldAvl.RChild = newAvl.LChild
	// newAvl.LChild = oldAvl
	// oldAvl.CountHeight()
	// newAvl.CountHeight()
	bt := RRRotation(avl)
	newAvl, _ := bt.(*AvlTree)
	newAvl.LChild.CountHeight()
	newAvl.CountHeight()
	return newAvl
}

//LR型 左子树的 右子树 更高
//        oldAvl            oldAvl            newAvl
//         /                /                 /    \
//       L1        ->   newAvl        ->    L1   oldAvl
//         \             /  \                 \    /
//       newAvl        L1    R2               L2  R2
//       /   \           \
//     L2    R2          L2     
func (avl *AvlTree)LRRotation()*AvlTree{
	avl.LChild = avl.LChild.RRRotation()
	return avl.LLRotation()
}



// RL型 右子树 的 左子树 更高
//     oldAvl             oldAvl                   newAvl
//         \                  \                    /    \
//         R1    ->         newAvl        ->    oldAvl   R1
//         /                 /  \                  \    /
//     newAvl              L2    R1                L2  R2
//     /   \                    /
//   L2    R2                 R2    
func (avl *AvlTree)RLRotation()*AvlTree{
	avl.RChild = avl.RChild.LLRotation()
	return avl.RRRotation()
}

// 计算平衡因子， 来判断调整形态，平衡因子为 左子树高度 - 右子树高度
func (avl *AvlTree)HandleBF()*AvlTree{
	lor := avl.LChild.GetHeight() - avl.RChild.GetHeight()
	if lor == 2{
		lor = avl.LChild.LChild.GetHeight() - avl.LChild.RChild.GetHeight()
		if lor > 0 { //LL
			return avl.LLRotation()
		}else{//LR
			return avl.LRRotation()
		}
	}else if lor == -2 {
		lor = avl.RChild.LChild.GetHeight() - avl.RChild.RChild.GetHeight()
		if lor < 0 { //RR
			return avl.RRRotation()
		}else{//RL
			return avl.RLRotation()
		}
	}
	return avl
}
